The present invention efficiently solves quadratic programs in real time. Such quadratic programs need to be solved to determine the best actuator commands to meet performance goals while satisfying constraints in Dynamic Inversion or Model Predictive Control of a dynamical system.
Time varying systems can be modeled by a set of linearized algebraic equations that relate the outputs and performance indices of the system to the inputs at every instant in time (in a nonlinear dynamical system, these equations change at every time instant). These inputs are formally known as control variables, because the values of these variables are under the control of the operator. The aim is to find the best sequence of control variables in time that maximize the performance indices of the system. In addition, the physical constraints of the system must be honored in order to prevent critical system failure. The problem of determining the best sequence of control variables requires solving a sequence of optimization problems in time, i.e., a new optimization problem at every instant in time. Each such optimization problem must be solved almost instantaneously. For the Dynamic Inversion application in systems with fast dynamics, this allows only a few milliseconds. Hence the requirement that the optimization technique come up with a solution swiftly is key in these applications. Two co-pending applications, “Real-Time Quadratic Programming For Control Of Dynamical Systems,” Ser. No. 10/308,285, filed Dec. 2, 2002, and “System and Method of Accelerated Active Set Search for Quadratic Programming in Real-Time Model Predictive Control,” Ser. No. 10/367,458, filed Feb. 14, 2003, the assignee of which is the assignee of the present invention, describe improved techniques for obtaining solutions efficiently.
The solution is restricted to a convex form, in general, and sometimes to quadratic programming, in order to ensure that a unique optimal solution exists, there are no local minima or maxima, and that the solution can be found with reasonable computation.
The algorithm also uses the active set method for solving realtime convex optimization problems, where the active set of a prior solution is “fedback” to initialize the search for the best active set in the current problem. This envisions application in a control system where the control solution is periodically updated at a high enough frequency that there is only little change from one update to the next. However, there are certain difficulties if the initial guess for the solution (the actuator commands) is infeasible and/or not consistent with the initial guess for the active set.
If the initial guess for the quadratic program is not feasible, the prior technique introduces an extra variable t (the big-K formulation). If a constraint that should be in the optimal active set is infeasible, it is relaxed, and the final solution from the big-K relaxed problem will always violate this constraint (setting the linear penalty with M>0 can correct for this).
There is a strong argument in favor of retaining consistency during the iterations, because otherwise the objective function may increase from one iteration to another, and a constraint may not satisfy the right hand side exactly even when it is declared active. Moreover, with an inconsistent start, if the solution to the first EQP violates any of the constraints, the current point becomes a convex combination of the EQP solution and xf (the initial guess for the feasible solution). Any constraint in the first active set that xf does not satisfy exactly must be dropped if consistency between the current iterate x and the active set were to be retained. This results in potentially promising constraints being dropped from the active set, thus losing the benefit of a good active set hot start.